package com.review.study;
  public class SortOperation {
    /**
     * 排序算法
     */
    Integer a;
    protected  NumberOperation numberOperation;

    public static void main(String[] args) {
        int[] b = {5, 6, 9, 0, 7, 5};
        int[] c = {1, 2, 3, 4, 5, 6, 7};
        bubbleSort2(b);
        for (int i : b
                ) {
            System.out.println(i);
        }
        int res = binarySearch(c, 5);
        System.out.println(res);
    }


    /**
     * 冒泡排序  时间复杂度
     *
     * @param a
     */
    public static void bubbleSort(int a[]) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }

        }

    }

    /**
     * 优化版 冒泡排序
     */
    public static void bubbleSort2(int a[]) {
        for (int i = 0; i < a.length; i++) {
            boolean flag = true;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = false;
                }

            }
            if (flag) {
                break;
            }
        }


    }

    /**
     * 直接选择排序
     */
    public static void selectSort(int a[]) {
        for (int i = 0; i < a.length; i++) {
            int index = i;
            for (int j = i; j < a.length; j++) {
                if (a[index] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }

            }
        }

    }

    /**
     * 直接选择排序优化
     */
    public static void selectSort2(int a[]) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i; j < a.length; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            if (i != min) {

                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
            }
        }

    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] a, int start, int end) {
        int i = start;
        int j = end;
        int base = a[(i + j) / 2];
        if (i > j) {
            System.out.println("参数输入有误");
        }
        while (i <= j) {
            while (a[i] < base)
                i++;
            while (j > base)
                j--;
            if (i <= j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        if (i < end) {
            quickSort(a, i, end);
        }
        if (j > start) {
            quickSort(a, start, j);
        }
    }

    /**
     * 插入排序
     */
    public static void insertSort(int a[]) {
        for (int i = 1; i < a.length; i++)
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    int tmp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = tmp;
                } else
                    break;
            }

    }

    /**
     * 插入法优化版
     */
    public static void insertSort2(int a[]) {
        int j;
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            for (j = i; j > 0; j--) {
                if (a[j - 1] > temp) {
                    a[j] = a[j - 1];
                } else
                    break;

            }
            a[j] = temp;
        }

    }

    /**
     * 二分搜索
     */
    public static int binarySearch(int a[], int base) {
        int left = 0;
        int right = a.length - 1;
        int middle;
        while (left <= right) {
            middle = (left + right) / 2;
            if (base < a[middle]) {
                right = middle - 1;
            } else if (base > a[middle]) {
                left = middle + 1;
            } else
                return middle;
        }
        return -1;

    }
}